package basic.sort.trie;

import java.util.HashMap;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.trie
 * @since JDK1.8
 */
public class TrieTree {

    // 字典树结点
    private static class Node1 {
        private int pass; // 经过的次数
        private int end; // 字符终结的次数
        private Node1[] nes; // next指针集

        public Node1() {
            pass = 0;
            end = 0;
            nes = new Node1[26];
        }
    }

    // 字典树
    private static class Trie1 {
        private Node1 root;

        public Trie1() {
            root = new Node1();
        }

        // 插入字符串
        private void insert(String str) {
            // 判断字符是否为空
            if (illegalStr(str)) {
                return;
            }

            // 转换成字符数组
            char[] chs = str.toCharArray();
            // 临时节点
            Node1 node = root;
            // 当前root经过次数++
            node.pass++;
            // 路径方向
            int location;
            // 循环添加字符
            for (char ch : chs) {
                // 路径方向
                location = ch - 'a';
                // 判断该字符是否曾经添加过
                if (node.nes[location] == null) {
                    node.nes[location] = new Node1();
                }
                // 变成相应节点
                node = node.nes[location];
                // 子节点经过次数++
                node.pass++;
            }
            // 当前节点作为一个字符串的结尾，则end++
            node.end++;
        }
        
        // 查找相应字符串
        private boolean search(String str) {
            // 判断字符是否为空
            if (illegalStr(str)) {
                return false;
            }

            // 转换成字符数组
            char[] chs = str.toCharArray();
            // 临时节点
            Node1 node = root;
            // 路径方向
            int location;
            // 循环删除字符
            for (char ch : chs) {
                // 路径方向
                location = ch - 'a';
                // 判断该路径是否为空
                if (node.nes[location] == null) {
                    return false;
                }
                // 向下
                node = node.nes[location];
            }

            return true;
        }
        
        // 删除字符串，需要回收内存空间
        private void delete(String str) {
            // 判断字符是否为空，或者有没有找到在树中该字符
            if (illegalStr(str) || !search(str)) {
                return;
            }

            // 转换成字符数组
            char[] chs = str.toCharArray();
            // 临时节点
            Node1 node = root;
            // 当前root经过次数++
            node.pass++;
            // 路径方向
            int location;
            // 循环删除字符
            for (char ch : chs) {
                // 路径方向
                location = ch - 'a';
                // 判断路径是否只经过依次，只经过一次，就可以直接设置为null
                if (node.nes[location].pass == 1) {
                    node.nes[location] = null;
                }
                // 删除经过次数
                node.nes[location].pass--;
                // 向下
                node = node.nes[location];
            }
            // 终结次数--
            node.end--;
        }

        // 当前前缀出现次数
        private int prefixNumber(String pre) {
            if (!illegalStr(pre)) {
                return 0;
            }

            // 转换成字符数组
            char[] chs = pre.toCharArray();
            // 临时节点
            Node1 node = root;
            // 路径方向
            int location;
            // 循环删除字符
            for (char ch : chs) {
                // 路径方向
                location = ch - 'a';
                // 判断路径是否提前结束
                if (node.nes[location] == null) {
                    return 0;
                }
                // 向下
                node = node.nes[location];
            }
            // 返回经过次数
            return node.pass;
        }
        
        // 判断字符串不合法
        private boolean illegalStr(String str) {
            return str == null || str.length() == 0;
        }

        public static class Node2 {
            public int pass;
            public int end;
            public HashMap<Integer, Node2> nexts;

            public Node2() {
                pass = 0;
                end = 0;
                nexts = new HashMap<>();
            }
        }

        public static class Trie2 {
            private Node2 root;

            public Trie2() {
                root = new Node2();
            }

            public void insert(String word) {
                if (word == null) {
                    return;
                }
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass++;
                int index = 0;
                for (char ch : chs) {
                    index = (int) ch;
                    if (!node.nexts.containsKey(index)) {
                        node.nexts.put(index, new Node2());
                    }
                    node = node.nexts.get(index);
                    node.pass++;
                }
                node.end++;
            }

            public void delete(String word) {
                if (!search(word)) {
                    char[] chs = word.toCharArray();
                    Node2 node = root;
                    node.pass--;
                    int index = 0;
                    for (char ch : chs) {
                        index = (int) ch;
                        if (--node.nexts.get(index).pass == 0) {
                            node.nexts.remove(index);
                            return;
                        }
                        node = node.nexts.get(index);
                    }
                    node.end--;
                }
            }

            // word这个单词之前加入过几次
            public boolean search(String word) {
                if (word == null) {
                    return false;
                }
                char[] chs = word.toCharArray();
                Node2 node = root;
                int index = 0;
                for (char ch : chs) {
                    index = (int) ch;
                    if (!node.nexts.containsKey(index)) {
                        return false;
                    }
                    node = node.nexts.get(index);
                }
                return true;
            }

            // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
            public int prefixNumber(String pre) {
                if (pre == null) {
                    return 0;
                }
                char[] chs = pre.toCharArray();
                Node2 node = root;
                int index = 0;
                for (char ch : chs) {
                    index = (int) ch;
                    if (!node.nexts.containsKey(index)) {
                        return 0;
                    }
                    node = node.nexts.get(index);
                }
                return node.pass;
            }
        }

        public static class Right {

            private HashMap<String, Integer> box;

            public Right() {
                box = new HashMap<>();
            }

            public void insert(String word) {
                if (!box.containsKey(word)) {
                    box.put(word, 1);
                } else {
                    box.put(word, box.get(word) + 1);
                }
            }

            public void delete(String word) {
                if (box.containsKey(word)) {
                    if (box.get(word) == 1) {
                        box.remove(word);
                    } else {
                        box.put(word, box.get(word) - 1);
                    }
                }
            }

            public boolean search(String word) {
                return box.containsKey(word);
            }

            public int prefixNumber(String pre) {
                int count = 0;
                for (String cur : box.keySet()) {
                    if (cur.startsWith(pre)) {
                        count += box.get(cur);
                    }
                }
                return count;
            }
        }

        // for test
        public static String generateRandomString(int strLen) {
            char[] ans = new char[(int) (Math.random() * strLen) + 1];
            for (int i = 0; i < ans.length; i++) {
                int value = (int) (Math.random() * 6);
                ans[i] = (char) (97 + value);
            }
            return String.valueOf(ans);
        }

        // for test
        public static String[] generateRandomStringArray(int arrLen, int strLen) {
            String[] ans = new String[(int) (Math.random() * arrLen) + 1];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = generateRandomString(strLen);
            }
            return ans;
        }

        public static void main(String[] args) {
            int arrLen = 100;
            int strLen = 20;
            int testTimes = 100000;
            for (int i = 0; i < testTimes; i++) {
                String[] arr = generateRandomStringArray(arrLen, strLen);
                Trie1 trie1 = new Trie1();
                Trie2 trie2 = new Trie2();
                Right right = new Right();
                for (String s : arr) {
                    double decide = Math.random();
                    if (decide < 0.25) {
                        trie1.insert(s);
                        trie2.insert(s);
                        right.insert(s);
                    } else if (decide < 0.5) {
                        trie1.delete(s);
                        trie2.delete(s);
                        right.delete(s);
                    } else if (decide < 0.75) {
                        boolean ans1 = trie1.search(s);
                        boolean ans2 = trie2.search(s);
                        boolean ans3 = right.search(s);
                        if (ans1 != ans2 || ans2 != ans3) {
                            System.out.println("Oops!");
                        }
                    } else {
                        int ans1 = trie1.prefixNumber(s);
                        int ans2 = trie2.prefixNumber(s);
                        int ans3 = right.prefixNumber(s);
                        if (ans1 != ans2 || ans2 != ans3) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
            System.out.println("finish!");

        }
        
    }
}
